package com.xiaolin.algorithm.dynamic;

import java.util.Arrays;

/**
 * @ClassName GatherCoins
 * @Description 凑零钱问题-使用动态规划求解
 * @Detail 凑出指定的金额至少需要多少枚硬币
 * @Author     其动态规划状态方程(n指的是要凑够的金额)：
 *                      1、if(n<0)  -1
 *                      2、if(n==0)  0
 *                      3、f(n)=f(n-1)+1
 * @Date 2020/11/21
 * @Version 1.0
 */
public class GatherCoins {
    public static void main(String[] args) {
        int[] coins=new int[]{1,2,5};
        int amount=35;
        long s1 = System.currentTimeMillis();
        System.out.println(gatherCoins(coins,amount));
        System.out.println(System.currentTimeMillis()-s1);
    }


    /**
     *  凑零钱-暴力递归
     * @param coins  硬币的面值，每个面值的硬币数量是无限的
     * @param amount  要凑够的总额
     * @return 能够凑出则返回需要的硬币数量，不能凑出则返回-1
     */
    public static int gatherCoins(int[] coins,int amount){
        return recursion(coins,amount);
    }

    public static int recursion(int[] coins,int amount){
        if(amount<0)return -1;
        if(amount==0)return 0;
        // 结果取无穷大
        int count=Integer.MAX_VALUE;
        for (int coin : coins) {
            int childCount = recursion(coins, amount - coin);
            if(childCount==-1)continue;
            count=Math.min(count,childCount+1);
        }
        return count!=Integer.MAX_VALUE ? count : -1;
    }

}
